package com.ocean.stack;

/**
 * https://leetcode.cn/problems/backspace-string-compare/
 * 比较含退格的字符串
 */
public class BackspaceStringCompare2 {
    public static void main(String[] args) {
        BackspaceStringCompare2 backspaceStringCompare = new BackspaceStringCompare2();
        boolean res = backspaceStringCompare.backspaceCompare2("a#b", "aa##b");
        System.out.println(res);
        res = backspaceStringCompare.backspaceCompare2("#cd#", "c");
        System.out.println(res);
        res = backspaceStringCompare.backspaceCompare2("#cd##", "c");
        System.out.println(res);
    }

    /**
     * 使用栈思路
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }


    private String build(String str) {
        StringBuilder buffer = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char charAt = str.charAt(i);
            if ('#' != charAt) {
                buffer.append(charAt);
            } else {
                if (buffer.length() > 0) {
                    buffer.deleteCharAt(buffer.length() - 1);
                }
            }
        }
        return buffer.toString();
    }

    /**
     * a#b aa##b
     * 边界情况：
     * #a  #a
     * #a  ##
     * #a  a
     * #a  a#
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare2(String s, String t) {
        if (s == null) {
            return false;
        }
        if (t == null) {
            return false;
        }
        // 遇到#就跳过
        int i = s.length() - 1;
        int j = t.length() - 1;
        int skipS = 0;
        int skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                char curS = s.charAt(i);
                if ('#' == curS) {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                char curT = t.charAt(j);
                if ('#' == curT) {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            // 这里比较 到这里 i和j有两种情况： (i<0) || (i>0&&skipS<0)   (j<0) || (j>0&&skipT<0)
            // 这里就有四种组合  i<0&&j<0 i<0&&j>=0  i>0&&j>=0 i>0&&j<0
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
                // 说明有一个小于0的
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            // 比较通过后 要移动指针 继续比较
            i--;
            j--;
        }
        return true;
    }
}
